\chapter{Вопрос №14}

Решение задач о раскладке различимых предметов по различимым ящикам с помощью экспоненциальных производящих функций.

\section{Вводные замечания, простейший случай}

Пусть имеется $n$ различных предметов и ровно 2 ящика, сколькими способами можно разложить предметы по ящикам без учета порядка предметов в ящике? Эта задача эквивалентна разбиению $n$-множества на два блока.

Если рассуждать в терминах произведений эпф, то мы должны $\binom{n}{k}$ способами разбить множество на 2 блока, а затем, каждый блок одним способом положить в соответствующий ящик, т. е. имеем пару эпф следующего вида:
\[
	F\left(x\right) = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + ... = exp\left(x\right) 
\]
а их произведение описывает результат:
\[
	H\left(x\right) = F\left(x\right)^2 = exp\left(2x\right) = \sum_{n=0}^\infty \frac{\left(2x\right)^n}{n!}
\]
т. е. для $n$-ого коэффициента $c_n$ функции $H\left(x\right)$:
\[
	c_n = \sum_{i=0}^n \binom{n}{i} = 2^n
\]

\section{Произвольное число ящиков}

Пусть теперь у нас имеется проивзольное число $k$ ящиков, тогда по аналогичным рассуждениям получаем:
\[
	H\left(x\right) = F\left(x\right)^k = exp\left(kx\right) = \sum_{n=0}^\infty \frac{\left(kx\right)^n}{n!}
\]
а соответствующий коэффициент $c_n$ выглядит следующим образом:
\[
	c_n = \sum_{i_1+...+i_k=n}P\left(n;i_1,...,i_k\right) = k^n
\]

\section{Не более одного предмета в ящике}

Если у нас есть такое ограничение, то уже нельзя использовать эпф $exp\left(x\right)$, а вместо этого очевидно необходима функция:
\[
	F\left(x\right) = 1 + x
\]
а ответ будет описываться следующим соотношением:
\[
	H\left(x\right) = F\left(x\right)^k = \left(1+x\right)^k = \sum_{i=0}^\infty \binom{k}{i}x^k = \sum_{i=0}^\infty \Lowerfact{k}{i} \frac{x^i}{i!}
\]

Аналогичным образом ешаются задачи с произвольными ограничениям на число элементов в ящике.

\section{Сюрьективные отображения}

Пусть теперь в каждом ящике должен быть хотябы один элемент, тогда используем следующую производящую функцию:
\[
	F\left(x\right) = exp\left(x\right) - 1
\]
а ответ имеет вид:
\[
	H\left(x\right) = F\left(x\right)^k = \left(exp\left(x\right)-1\right)^k = \sum_{i=0}^k\left(-1\right)^i \binom{k}{i} exp\left(\left(k-i\right)x\right)
\]
где
\[
	exp\left(\left(k-i\right)x\right) = \sum_{l=0}^\infty \left(k-i\right)^l\frac{x^l}{l!}
\]
подставляем назад:
\[
	\begin{split}
		& H\left(x\right) = \sum_{i=0}^k\left(-1\right)^i\binom{k}{i}\sum_{n=0}^\infty \left(k-i\right)^n \frac{x^n}{n!} = \\
		& = \sum_{n=0}^\infty \frac{x^n}{n!} \left[\sum_{i=0}^k \left(-1\right)^i\binom{k}{i}\left(k-i\right)^n\right] = \sum_{n=0}^\infty \hat S\left(n,k\right) \frac{x^n}{n!}
	\end{split}
\]
